use std::{
    collections::HashMap,
    ops::{Deref, DerefMut},
};

struct Node {
    pass: u32,
    end: u32,
    next: HashMap<char, NodeLink>,
}
impl Node {
    fn new() -> Self {
        Self {
            pass: 0,
            end: 0,
            next: HashMap::new(),
        }
    }
}

struct NodeLink(Box<Node>);
impl Deref for NodeLink {
    type Target = Box<Node>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl DerefMut for NodeLink {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl NodeLink {
    fn new() -> Self {
        Self(Box::new(Node::new()))
    }

    fn from(strs: &[&str]) -> Self {
        let mut root = NodeLink::new();
        let mut node = &mut root;

        for s in strs {
            node.pass += 1;
            for c in s.chars() {
                node = node.next.entry(c).or_insert(NodeLink::new());
                node.pass += 1;
            }
            node.end += 1;
            node = &mut root;
        }

        root
    }

    fn print_recursion(&self, node: &NodeLink) {
        print!("(p:{}, e:{}) ", node.pass, node.end);

        if node.next.len() == 0 {
            println!("return");
            return;
        }

        for (c, next) in &node.next {
            print!("-->{}", c);
            self.print_recursion(next);
        }
    }

    fn print(&self) {
        self.print_recursion(self)
    }

    fn prefix_times(&self, s: &str) -> Option<u32> {
        if s == "" {
            return Some(self.end);
        }

        let mut node = self;
        for c in s.chars() {
            if node.next.get(&c).is_none() {
                return None;
            }
            node = node.next.get(&c).unwrap();
        }

        Some(node.pass)
    }

    fn search(&self, s: &str) -> u32 {
        if s == "" {
            return self.end;
        }

        let mut node = self;
        for c in s.chars() {
            if node.next.get(&c).is_none() {
                return 0;
            }
            node = node.next.get(&c).unwrap();
        }

        node.end
    }

    fn delete(&mut self, s: &str) {
        if self.search(s) == 0 {
            return;
        }

        let mut node = self;
        node.pass -= 1;

        for c in s.chars() {
            if node.next.get(&c).unwrap().pass == 1 {
                node.next.remove(&c);
                return;
            }
            node = node.next.get_mut(&c).unwrap();
            node.pass -= 1;
        }
        node.end -= 1;
    }
}

fn queen_valid(x: i32, y: i32, v: &mut [i32]) -> bool {
    for y0 in 0..y {
        if x == v[y0 as usize] || ((y0 - y).abs() == (v[y0 as usize] - x).abs()) {
            return false;
        }
    }
    true
}

fn queen(y: i32, n: i32, v: &mut [i32]) -> i32 {
    if y == n {
        print!("[");
        for (y, x) in v.iter().enumerate() {
            print!("({}, {}), ", x, y);
        }
        println!("]");
        return 1;
    }

    let mut res = 0;
    for x in 0..n {
        if queen_valid(x, y, v) {
            v[y as usize] = x;
            res += queen(y + 1, n, v);
        }
    }
    if res == 0 {
        v[(y - 1) as usize] = 0;
    }
    res
}

pub fn trie_main() {
    let mut tree = NodeLink::from(&["abc", "abd", "abe", "bc", "bce"]);
    tree.print();

    let s = "abc";
    println!(
        "{} as {:?} times prefix, as string: {:?}",
        s,
        tree.prefix_times(s),
        tree.search(s)
    );
    let s = "ab";
    println!(
        "{} as {:?} times prefix, as string: {:?}",
        s,
        tree.prefix_times(s),
        tree.search(s)
    );
    let s = "bc";
    println!(
        "{} as {:?} times prefix, as string: {:?}",
        s,
        tree.prefix_times(s),
        tree.search(s)
    );
    let s = "bd";
    println!(
        "{} as {:?} times prefix, as string: {:?}",
        s,
        tree.prefix_times(s),
        tree.search(s)
    );
    let s = "b";
    println!(
        "{} as {:?} times prefix, as string: {:?}",
        s,
        tree.prefix_times(s),
        tree.search(s)
    );

    println!("========= 删除字符串 =========");
    tree.print();
    let s = "abd";
    println!("删除{}", s);
    tree.delete(s);
    tree.print();
    let s = "ab";
    println!("删除{}", s);
    tree.delete(s);
    tree.print();
    let s = "abc";
    println!("删除{}", s);
    tree.delete(s);
    tree.print();

    println!("========= N皇后问题 =========");
    let mut v = [0; 4];
    let num = queen(0, 4, &mut v);
    println!("{}", num);
}
